/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.array

import org.jheaps.Constants
import org.jheaps.annotations.ConstantTime
import org.jheaps.annotations.LinearTime
import org.jheaps.annotations.LogarithmicTime
import java.io.Serializable
import java.util.*

/**
 * An array based binary weak heap. The heap is sorted according to the
 * [natural ordering][Comparable] of its keys, or by a
 * [Comparator] provided at heap creation time, depending on which
 * constructor is used.
 *
 *
 *
 * The implementation uses an array in order to store the elements and
 * automatically maintains the size of the array much like a
 * [java.util.Vector] does, providing amortized O(log(n)) time cost for
 * the `insert` and `deleteMin` operations. Operation
 * `findMin`, is a worst-case O(1) operation. The bounds are worst-case if
 * the user initializes the heap with a capacity larger or equal to the total
 * number of elements that are going to be inserted into the heap.
 *
 *
 *
 * Constructing such a heap from an array of elements can be performed using the
 * method [.heapify] or [.heapify]
 * in linear time.
 *
 *
 *
 * Note that the ordering maintained by a binary heap, like any heap, and
 * whether or not an explicit comparator is provided, must be *consistent
 * with `equals`* if this heap is to correctly implement the
 * `Heap` interface. (See `Comparable` or `Comparator` for a
 * precise definition of *consistent with equals*.) This is so because
 * the `Heap` interface is defined in terms of the `equals`
 * operation, but a binary heap performs all key comparisons using its
 * `compareTo` (or `compare`) method, so two keys that are deemed
 * equal by this method are, from the standpoint of the binary heap, equal. The
 * behavior of a heap *is* well-defined even if its ordering is
 * inconsistent with `equals`; it just fails to obey the general contract
 * of the `Heap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 *
 * @author Dimitrios Michail
</K> */
open class BinaryArrayWeakHeap<K> : AbstractArrayWeakHeap<K>, Serializable {
    /**
     * Reverse bits
     */
    protected var reverse: BitSet?=null

    /**
     * Constructs a new, empty heap, using the natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is
     * [BinaryArrayWeakHeap.DEFAULT_HEAP_CAPACITY] and adjusts
     * automatically based on the sequence of insertions and deletions.
     */
    constructor() : super(null, DEFAULT_HEAP_CAPACITY)

    /**
     * Constructs a new, empty heap, with a provided initial capacity using the
     * natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions. The
     * capacity will never become smaller than the initial requested capacity.
     *
     * @param capacity
     * the initial heap capacity
     */
    constructor(capacity: Int) : super(null, capacity)

    /**
     * Constructs a new, empty heap, ordered according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is
     * [BinaryArrayWeakHeap.DEFAULT_HEAP_CAPACITY] and adjusts
     * automatically based on the sequence of insertions and deletions.
     *
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     */
    constructor(comparator: Comparator<in K?>?) : super(comparator, DEFAULT_HEAP_CAPACITY)

    /**
     * Constructs a new, empty heap, with a provided initial capacity ordered
     * according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions. The
     * capacity will never become smaller than the initial requested capacity.
     *
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     * @param capacity
     * the initial heap capacity
     */
    constructor(comparator: Comparator<in K?>?, capacity: Int) : super(comparator, capacity)

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun findMin(): K {
        if (Constants.NOT_BENCHMARK && size == 0) {
            throw NoSuchElementException()
        }
        return array[0]!!
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime(amortized = true)
    override fun insert(key: K) {
        if (Constants.NOT_BENCHMARK) {
            if (key == null) {
                throw NullPointerException("Null keys not permitted")
            }
            // make sure there is space
            if (size == array.size) {
                if (size == 0) {
                    ensureCapacity(1)
                } else {
                    ensureCapacity(2 * array.size)
                }
            }
        }

        array[size] = key
        reverse!!.clear(size)

        if (size % 2 == 0) {
            reverse!!.clear(size / 2)
        }

        if (comparator == null) {
            fixup(size)
        } else {
            fixupWithComparator(size)
        }

        ++size
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime(amortized = true)
    override fun deleteMin(): K {
        if (Constants.NOT_BENCHMARK && size == 0) {
            throw NoSuchElementException()
        }

        val result: K = array[0]!!

        size--
        array[0] = array[size]
        array[size] = null

        if (size > 1) {
            if (comparator == null) {
                fixdown(0)
            } else {
                fixdownWithComparator(0)
            }
        }

        if (Constants.NOT_BENCHMARK) {
            if (2 * minCapacity <= array.size && 4 * size < array.size) {
                ensureCapacity(array.size / 2)
            }
        }
        return result
    }

    override fun initCapacity(capacity: Int) {
        this.array = arrayOfNulls<Any>(capacity) as Array<K?>
        this.reverse = BitSet(capacity)
    }

    /**
     * Ensure that the array representation has the necessary capacity.
     *
     * @param capacity
     * the requested capacity
     */
    override fun ensureCapacity(capacity: Int) {
        checkCapacity(capacity)
        val newArray: Array<K?> = arrayOfNulls<Any>(capacity) as Array<K?>
        System.arraycopy(array, 0, newArray, 0, size)
        array = newArray
        val newBitSet: BitSet = BitSet(capacity)
        newBitSet.or(reverse)
        reverse = newBitSet
    }

    /**
     * Return the distinguished ancestor of an element.
     *
     * @param j
     * the element
     * @return the distinguished ancestor of the element
     */
    protected fun dancestor(j: Int): Int {
        var j: Int = j
        while ((j % 2 == 1) == reverse!!.get(j / 2)) {
            j /= 2
        }
        return j / 2
    }

    /**
     * Join two weak heaps into one.
     *
     * @param i
     * root of the first weak heap
     * @param j
     * root of the second weak heap
     * @return true if already a weak heap, false if a flip was needed
     */
    protected fun join(i: Int, j: Int): Boolean {
        if ((array[j] as Comparable<K>).compareTo(array[i]!!) < 0) {
            val tmp = array[i]
            array[i] = array[j]
            array[j] = tmp
            reverse!!.flip(j)
            return false
        }
        return true
    }

    /**
     * Join two weak heaps into one.
     *
     * @param i
     * root of the first weak heap
     * @param j
     * root of the second weak heap
     * @return true if already a weak heap, false if a flip was needed
     */
    protected fun joinWithComparator(i: Int, j: Int): Boolean {
        if (comparator!!.compare(array[j], array[i]) < 0) {
            val tmp = array[i]
            array[i] = array[j]
            array[j] = tmp
            reverse!!.flip(j)
            return false
        }
        return true
    }

    override fun fixup(j: Int) {
        var j: Int = j
        var i: Int
        while (j > 0) {
            i = dancestor(j)
            if (join(i, j)) {
                break
            }
            j = i
        }
    }

    override fun fixupWithComparator(j: Int) {
        var j: Int = j
        var i: Int
        while (j > 0) {
            i = dancestor(j)
            if (joinWithComparator(i, j)) {
                break
            }
            j = i
        }
    }

    override fun fixdown(j: Int) {
        var k: Int = 2 * j + (if (reverse!!.get(j)) 0 else 1)
        var c: Int
        while (((2 * k + (if (reverse!!.get(k)) 1 else 0)).also { c = it }) < size) {
            k = c
        }
        while (k != j) {
            join(j, k)
            k = k / 2
        }
    }

    override fun fixdownWithComparator(j: Int) {
        var k: Int = 2 * j + (if (reverse!!.get(j)) 0 else 1)
        var c: Int
        while (((2 * k + (if (reverse!!.get(k)) 1 else 0)).also { c = it }) < size) {
            k = c
        }
        while (k != j) {
            joinWithComparator(j, k)
            k /= 2
        }
    }

    companion object {
        /**
         * Default initial capacity of the binary heap.
         */
        val DEFAULT_HEAP_CAPACITY: Int = 16

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param array
         * an array of elements
         * @return a heap
         * @throws IllegalArgumentException
         * in case the array is null
        </K> */
        @JvmStatic
        @LinearTime
        fun <K> heapify(array: Array<K>): BinaryArrayWeakHeap<K> {
            if (array == null) {
                throw IllegalArgumentException("Array cannot be null")
            }
            if (array.size == 0) {
                return BinaryArrayWeakHeap()
            }

            val h: BinaryArrayWeakHeap<K> = BinaryArrayWeakHeap(array.size)

            System.arraycopy(array, 0, h.array, 0, array.size)
            h.size = array.size

            for (j in h.size - 1 downTo 1) {
                h.join(h.dancestor(j), j)
            }

            return h
        }

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param array
         * an array of elements
         * @param comparator
         * the comparator to use
         * @return a heap
         * @throws IllegalArgumentException
         * in case the array is null
        </K> */
        @JvmStatic
        @LinearTime
        fun <K> heapify(array: Array<K>, comparator: Comparator<in K?>?): BinaryArrayWeakHeap<K> {
            if (array == null) {
                throw IllegalArgumentException("Array cannot be null")
            }
            if (array.isEmpty()) {
                return BinaryArrayWeakHeap(comparator)
            }

            val h: BinaryArrayWeakHeap<K> = BinaryArrayWeakHeap(comparator, array.size)

            System.arraycopy(array, 0, h.array, 0, array.size)
            h.size = array.size

            for (j in h.size - 1 downTo 1) {
                h.joinWithComparator(h.dancestor(j), j)
            }

            return h
        }
    }
}
